package Hot100.Easy.LC121;

public class LC121 {
    public static void main(String[] args) {
        int[] nums={7,1,5,3,6,4};
        int[] nums1={7,6,4,3,1};
        LC121 test=new LC121();
        System.out.println(test.maxProfit1(nums));
    }
    //暴力法，双循环
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length; j++) {
                profit=Math.max(profit, prices[j]-prices[i]);
            }
        }
        return profit;
    }
    //动态规划，遍历的时候记录目前为止最低的价格，并计算卖出时的利润
    public int maxProfit1(int[] prices) {
        int profit = 0;
        int minPrice=Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            minPrice=Math.min(minPrice,prices[i]);
            profit=Math.max(profit,prices[i]-minPrice);
        }
        return profit;
    }
}
